Searching for a particular sequence of data in a continuous serial bit stream is a process that has traditionally taken a long period of time, and has more recently been very software and computer processor intensive. FIG. 1 depicts a classical implementation of the search for a requested eight bit data pattern contained within a data stream. As is shown in FIG. 1, a data stream 100 comprises a number of data bits D−n . . . D0, D1 . . . D+n, In FIG. 1, bits D0-D7 are currently located in a shift register 120. Bits D8 and higher of data stream 100 have already been output from shift register 120. Bits D−1 and lower of bit stream 100 have not yet been entered in shift register 120. The eight bit data pattern that is to be searched for is stored into a second register 130, and includes bits C0-C7. While eight bits are shown, any number of bits could be employed.
To determine whether the desired bit pattern ins present in the data stream, the portion of the bit stream in shift register 120 is compared to the eight bit data pattern stored in register 130 on a bit by bit basis through the use of an eight bit comparator 140. If all bits are the same, the comparator determines that the data currently in the shift register is the requested data pattern. If the bits are not all the same, then at each bit rate period one new bit is shifted into the shift register pushing all the other bits to the right by one position. Thus, after a first comparison has failed, bit D7 id output from the shift register, bits D6-D0 are shifted one bit to the right, and bit D−1 is loaded into the shift register. After the shifting procedure is completed, once again the comparator compares the new data in the shift register to the requested data pattern.
An attempt to improve on this design has been set forth in U.S. Pat. No. 4,802,192 issued to Eto. et al. In this patent, a system is described that divides a 16-bit sequence into four portions, and then each comparator performs a search for a portion (1/n) bits of the overall pattern. A major drawback of this method is that even though the comparators are each running at a 1/n frequency, the outputs from the various comparators and the internal timing and clocks of the comparators must be very tightly controlled in order to recombine the low speed output data from the n comparators to generate one high speed result. Additionally, even in such a solution, it is necessary to perform four comparisons with each four bit comparator, or 16 comparisons, to determine the proper sequence. While this system does allow some parallel processing, it does not reduce the overall number of comparisons, and in fact, while reducing complexity in one respect, in creases the required complexity of the overall timing and control system.
These prior art approaches suffer at least one major problem when applied to data running at a high speed, such as a multi gigabit serial transmission. The comparator (or set of comparators) is required to operate at the bitrate frequency and may require a custom design using extremely high-speed technology.